package main

import "sort"

//#link: https://leetcode-cn.com/problems/find-kth-largest-xor-coordinate-value/
func main() {

}

//计算前缀和，用二维数组保留每个格子的异或前缀和 即 pre[i][j]=pre[i-1][j]^pre[i][j-1]^pre[i-1][j-1]^matrix[i][j],然后排序获得第k大的值
func kthLargestValue(matrix [][]int, k int) int {
	m, n := len(matrix), len(matrix[0])
	result := make([]int, 0, m*n)
	preMatrix := make([][]int, m+1)
	preMatrix[0] = make([]int, n+1)
	for i, column := range matrix {
		preMatrix[i+1] = make([]int, n+1)
		for j, row := range column {
			preMatrix[i+1][j+1] = preMatrix[i+1][j] ^ preMatrix[i][j+1] ^ preMatrix[i][j] ^ row
			result = append(result, preMatrix[i+1][j+1])
		}
	}
	sort.Sort(sort.Reverse(sort.IntSlice(result)))
	return result[k-1]
}
